package com.togo.algorithm.easy.search;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author taiyn
 * @Description
 * 找出数组中重复的数字。
 *
 *
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 *
 * 示例 1：
 *
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 *  
 *
 * 限制：
 *
 * 2 <= n <= 100000
 *
 * @Date 11:12 AM 2023/5/25
 **/
public class Offer03 {

    public int findRepeatNumberByHashTable(int[] nums) {

        Set<Integer> dic = new HashSet<>();
        for(int i : nums) {
            if(dic.contains(i)) return i;
            dic.add(i);
        }

        return -1;
    }

    public int findRepeatNumberByArray(int[] nums) {

        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }

            int j = nums[i];
            if(nums[j] == j) {
                return j;
            }

            nums[i] = nums[j];
            nums[j] = j;
        }

        return -1;
    }

    public static void main(String[] args) {

        Offer03 offer03 = new Offer03();
        int[] arr = {3,4,2,1,1,0};
        offer03.findRepeatNumberByArray(arr);
    }
}
